/**
 * @author: lk
 * @data: 2021/11/10 14:21
 */
package LeetCode;

import insertionSort.InsertionSort;
import selectionSort.ArrayGenerator;

import java.util.Arrays;

/**
 * 逆序数对个数。用归并排序实现
 */
public class Offer51 {
    public int reversePairs(int[] nums) {
        int[] temp = Arrays.copyOf(nums, nums.length);
        return sort(nums, 0, nums.length - 1, temp);
    }

    private int sort(int[] arr, int l, int h, int[] temp) {
        if (l >= h)
            return 0;
        int mid = (l + h) / 2;
        sort(arr, l, mid, temp);
        sort(arr, mid + 1, h, temp);
        return merge(arr, l, mid, h, temp);
    }

    private int merge(int[] arr, int l, int mid, int h, int[] temp) {
        System.arraycopy(arr, l, temp, l, h - l + 1);
        int low = l, high = mid+1, res = 0;
        for (int i = l; i <= h; i++) {
            if (low > mid) {
                arr[i] = temp[high];
                high++;
            } else if (high > h) {
                arr[i] = temp[low];
                low++;
            } else if (temp[low] <= temp[high]) {
                arr[i] = temp[low];
                low++;
            } else {
                arr[i] = temp[high];
                res+=(h-high+1);//关键句：若temp[high]<temp[low]则说明temp[high]<temp[low,h]，对应h-high+1个逆序对。
                high++;
            }

        }

        return res;
    }


    public static void main(String[] args) {
        int n = 4;
        int[] arr = ArrayGenerator.generateIntRandomArray(n, n);
        System.out.println(new Offer51().reversePairs(arr));
    }
}
